#include "link_list.h"

// 创建链表节点的函数--使用地址传参实现  返回值方式也能实现 很简单课下自己写
int create_node(node_t **p, int num){
    if(NULL == p){
        printf("入参为NULL 请检查\n");
        return -1;
    }
    *p = (node_t *)malloc(sizeof(node_t));
    if(NULL == *p){
        printf("内存分配失败\n");
        return -1;
    }
    (*p)->data = num;
    (*p)->next = NULL;
    return 0;
}

// 向链表中插入元素(头插)
int insert_list_by_head(node_t *phead, int num){
    if(NULL == phead){
        printf("入参为NULL 请检查\n");
        return -1;
    }
    // 创建新节点
    node_t *pnew = NULL;
    create_node(&pnew, num);
    // 执行头插
    pnew->next = phead->next;
    phead->next = pnew;
    return 0;
}

// 打印链表中所有元素--实际不需要 只是学习阶段用来看现象的
int print_list(node_t *phead){
    if(NULL == phead){
        printf("入参为NULL 请检查\n");
        return -1;
    }
    node_t *ptemp = phead->next; 
    while(NULL != ptemp){
        printf("%d  ", ptemp->data);
        ptemp = ptemp->next; // 这行代码的作用在链表操作中真重要 类似于顺序表下标 i++
    }
    printf("\n");
    return 0;
}

// 向链表中插入元素(尾插)
int insert_list_by_tail(node_t *phead, int num){
    if(NULL == phead){
        printf("入参为NULL 请检查\n");
        return -1;
    }
    // 先遍历链表 找到最后一个节点
    node_t *ptemp = phead;
    while(NULL != ptemp->next){
        ptemp = ptemp->next;
    }
    // 创建新节点
    node_t *pnew = NULL;
    create_node(&pnew, num);
    // 让最后一个节点的指针域指向新节点
    ptemp->next = pnew;
    return 0;
}

// 向链表中插入元素(任意位置插)
int insert_list_by_pos(node_t *phead, int pos, int num){
    // 入参合法性检查
    if(NULL == phead){
        printf("入参为NULL 请检查\n");
        return -1;
    }
    // 插入位置合理性检查
    // 左侧位置合法性
    if(pos < 0){
        printf("位置不合理 插入失败\n");
        return -1;
    }
    // 一边找待插入位置的前一节点 一边判断右侧位置合法性
    node_t *ptemp = phead;
    int i = 0;
    // 如果想在pos位插入元素 应该保证 ptemp = ptemp->next; 执行pos次后 ptemp不是NULL
    for(i = 0; i < pos; i++){
        if(NULL == ptemp->next){
            break;
        }
        ptemp = ptemp->next;
    }
    if(i < pos){
        printf("位置不合理 插入失败\n");
        return -1;
    }
    // 创建新节点
    node_t *pnew = NULL;
    create_node(&pnew, num);
    // 执行插入操作
    pnew->next = ptemp->next;
    ptemp->next = pnew;
    return 0;
}

// 删除链表中的元素(头删)
int delete_list_by_head(node_t *phead){
    if(NULL == phead){
        printf("入参为NULL 请检查\n");
        return -1;
    }
    if(NULL == phead->next){
        printf("表空 删除失败\n");
        return -1;
    }
    node_t *pdel = phead->next;
#if 0
    phead->next = pdel->next;
#else
    // 上下两行代码是等价的
    phead->next = phead->next->next;
    // 注意 phead->next->next 要保证 phead->next不为NULL 才能再取next !!!
#endif
    free(pdel);
    pdel = NULL;
    return 0;
}

// 删除链表中的元素(尾删)
int delete_list_by_tail(node_t *phead){
    if(NULL == phead){
        printf("入参为NULL 请检查\n");
        return -1;
    }
    if(NULL == phead->next){
        printf("表空 删除失败\n");
        return -1;
    }
    // 遍历链表 找到倒数第二个节点
    node_t *ptemp = phead;
    while(NULL != ptemp->next->next){
        ptemp = ptemp->next;
    }
    // 执行删除操作
    free(ptemp->next);
    ptemp->next = NULL;
    return 0;
}

// 删除链表中的元素(任意位置删)
int delete_list_by_pos(node_t *phead, int pos){
    if(NULL == phead){
        printf("入参为NULL 请检查\n");
        return -1;
    }
    if(NULL == phead->next){
        printf("表空 删除失败\n");
        return -1;
    }
    if(pos < 0){
        printf("位置不合理 删除失败\n");
        return -1;
    }
    // 一边找待删除位置的前一节点 一边判断右侧位置合法性
    node_t *ptemp = phead;
    int i = 0;
    for(i = 0; i < pos; i++){
        if(NULL == ptemp->next->next){
            printf("位置不合理 删除失败\n");
            return -1;
        }
        ptemp = ptemp->next;
    }
    // 执行删除操作
    node_t *pdel = ptemp->next;
    ptemp->next = pdel->next;
    free(pdel);
    pdel = NULL;
    return 0;
}

// 修改链表指定位置的元素
int modify_list_by_pos(node_t *phead, int pos, int new_num){
    if(NULL == phead){
        printf("入参为NULL 请检查\n");
        return -1;
    }
    if(NULL == phead->next){
        printf("表空 修改失败\n");
        return -1;
    }
    if(pos < 0){
        printf("位置不合理 修改失败\n");
        return -1;
    }
    // 一边找待修改位置的前一节点 一边判断右侧位置合法性
    node_t *ptemp = phead;
    int i = 0;
    for(i = 0; i < pos; i++){
        if(NULL == ptemp->next->next){
            printf("位置不合理 修改失败\n");
            return -1;
        }
        ptemp = ptemp->next;
    }
    // 执行修改操作
    ptemp->next->data = new_num;
    return 0;
}

// 查找链表指定位置的元素
int search_list_by_pos(node_t *phead, int pos, int *buff){
    if(NULL == phead || NULL == buff){
        printf("入参为NULL 请检查\n");
        return -1;
    }
    if(NULL == phead->next){
        printf("表空 查找失败\n");
        return -1;
    }
    if(pos < 0){
        printf("指定的位置没有元素\n");
        return -1;
    }
    // 一边找待查找位置的前一节点 一边判断右侧位置合法性
    node_t *ptemp = phead;
    int i = 0;
    for(i = 0; i < pos; i++){
        if(NULL == ptemp->next->next){
            printf("指定的位置没有元素\n");
            return -1;
        }
        ptemp = ptemp->next;
    }
    // 执行查找操作
    *buff = ptemp->next->data;
    return 0;
}

// 清空链表
int clean_list(node_t *phead){
    if(NULL == phead){
        printf("入参为NULL 请检查\n");
        return -1;
    }
    // 循环头删所有数据节点即可
    // (尽量自己重新写逻辑  不要调用头删的函数)
    node_t *pdel = phead->next;
    while(NULL != phead->next){
        phead->next = pdel->next;
        free(pdel);
        pdel = phead->next;
    }
    pdel = NULL;
    return 0;
}

// 销毁链表
int destroy_list(node_t **p){
    if(NULL == p || NULL == *p){
        printf("入参为NULL 请检查\n");
        return -1;
    }
    // 销毁之前先清空 防止内存泄露(防止用户不清空就销毁)
    clean_list(*p);
    free(*p);
    *p = NULL;
    return 0;
}

// 合并两个链表
int hebing_list(node_t *phead1, node_t **phead2){
    if(NULL == phead1 || NULL == phead2 || NULL == *phead2){
        printf("入参为NULL 请检查\n");
        return -1;
    }
    // 先找phead1的最后一个节点
    node_t *ptemp = phead1;
    while(NULL != ptemp->next){
        ptemp = ptemp->next;
    }
    // 让phead1的最后一个节点的指针域指向phead2的第一个数据节点
    ptemp->next = (*phead2)->next;
    free(*phead2);
    *phead2 = NULL;
    return 0;
}

// 链表排序(升序为例)
int sort_list(node_t *phead){
    if(NULL == phead){
        printf("入参为NULL 请检查\n");
        return -1;
    }
    if(NULL == phead->next){
        printf("链表为空 无需排序\n");
        return -1;
    }
    if(NULL == phead->next->next){
        printf("链表只有一个数据节点 无需排序\n");
        return -1;
    }
    // 执行排序的流程
    node_t *p = phead->next;
    node_t *q = NULL;
    int temp = 0;
    while(NULL != p->next){
        q = p->next;
        while(NULL != q){
            if(p->data > q->data){
                temp = p->data;
                p->data = q->data;
                q->data = temp;
            }
            q = q->next;
        }
        p = p->next;
    }
    return 0;
}

// 链表翻转
int overtrun_list(node_t *phead){
    if(NULL == phead){
        printf("入参为NULL 请检查\n");
        return -1;
    }
    if(NULL == phead->next){
        printf("链表为空 无需翻转\n");
        return -1;
    }
    if(NULL == phead->next->next){
        printf("链表只有一个数据节点 无需翻转\n");
        return -1;
    }
    // 执行翻转操作
    node_t *p = phead->next;
    node_t *q = p->next;
    p->next = NULL;
    while(NULL != q){
        p = q->next;
        q->next = phead->next;
        phead->next = q;
        q = p;
    }
    return 0;
}

// 链表剔重
int tichong_list(node_t *phead){
    if(NULL == phead){
        printf("入参为NULL 请检查\n");
        return -1;
    }
    if(NULL == phead->next){
        printf("链表为空 无需剔重\n");
        return -1;
    }
    if(NULL == phead->next->next){
        printf("链表只有一个数据节点 无需剔重\n");
        return -1;
    }
    // 执行剔重操作
    node_t *p = phead->next;
    node_t *m = NULL; // m一直保存q的前一节点 删除q时使用
    node_t *q = NULL;
    while(NULL != p){
        m = p;
        q = p->next;
        while(NULL != q){
            if(p->data != q->data){
                m = q;
                q = q->next;
            }else{
                m->next = q->next;
                free(q);
                q = m->next;
            }
        }
        p = p->next;
    }
    return 0;
}